整数 Double Dabble 算法

（下文当中，“BCD 位” 指一个十进制位对应的四位二进制）

首先，如果我们要计算一个二进制数的十进制值，除了位权展开以外，可以从左往右如此迭代： \[ x_{n + 1} = 2x_n + \text {该二进制位} \] 这是非常显然的。

在 Double Dabble 的图示当中，左边一列存储的是 BCD 的结果：

Double Dabble 算法本身其实就是在这 BCD 的结果列进行如上的迭代操作（乘 \(2\) 加位）。

为了这样做，直觉上来讲，我们可以按照二进制的方法将 BCD 列中的结果乘 \(2\)（左移），然后进行一定的矫正（之前的左移可能破坏了 BCD 的性质），然后在加上原数的一个二进制位（最右边移进）。

左移是平凡的，加上一位也是平凡的（因为左移之后最右边一位永远是 \(2\)，不会产生进位），问题在乘 \(2\) 后为了维护 BCD 性质所进行的矫正上。

首先，我们应该注意到，忽略进位，如果一个 BCD 位大于 \(10\)，我们需要减 \(10\) 来获得正确的位，而减 \(10\) 在四位二进制意义下就等同于加 \(6\)，即 \(110_2\)。

Double Double 算法的首先高在它甚至在乘 \(2\) 之前就进行了矫正。我们考虑哪些 BCD 位乘 \(2\) 之后会出现问题，答案非常平凡：满 \(5\) 的。而因为是在左移之前，加上的 \(110_2\) 也就变成 \(11_2\)，即加 \(3\)。

这就是 “满五加三” 的由来。

不仅如此，Double Dabble 算法高在因为这是对于左移之前的四位进行的操作，因而加 \(3\) 之后会进位到四位当中的最高位，其左移之后就到左边的 BCD 位上去了… 相当于巧妙 handle 进位的问题。

小数 Double Dabble 算法

小数 Double Dabble 似乎没多少人提到…… 但是本质确实是和整数算法一致的。

我们进行小数二进制 - 十进制转化可以利用如下的从右往左的迭代过程： \[ x_{n + 1} = \frac {x_n + \text {该二进制位}}{2} \] 我们同样要对结果列进行这样的操作。

首先是 \(x_n + \text {该二进制位}\) 的部分，由于结果列现在表示小数部分，加上去的二进制列就在整个结果列的左侧（整数部分），这无疑是平凡的。

接下来是除 \(2\) 的部分。基于二进制的思想，我们通过右移来完成除 \(2\) 的操作。同时我们需要进行一定的矫正来维护 BCD 的性质。

我们观察到，出现问题的 BCD 位，一定是在右移之前是奇数的位，而奇数最低位上的 \(1\)，在右移之后，就到了右边的最高位上，也就是右边的哪一位右移之后会大于等于 \(8\)。

而回到十进制，如果一个奇数位除以二，结果应该给右边的位加上 \(5\)，而我们之前算法中右移过来的 \(1\) 让它加了 \(8\)，所以要减去 \(3\)。

这就是 “满八减三” 的由来。